/**
 * 最少也要对所有元素遍历一遍
 * 要求用时间最少，那么申请辅助空间即可
 * 
 * 一个新的链表用来存储到来的数据
 * 一个数组做直接hash，标记[i]的绝对值是否已经存储到链表中
 */

#include"LinkedList.h"
#include<stdlib.h>
/**
 * @param head 单链表，有头节点
 * n是链表元素范围
 */
void func(LinkedList *head,int n){
    LinkedList*p=head,*r;
    int *q,m;
    q=(int*)malloc(sizeof(int)*(n+1));//cpp的话改成new吧
    for(int i=0;i<n+1;i++){//标记数组初始化为全0
        q[i]=0;
    }
    while (p->next!=NULL)//一直往下遍历
    {
        //获取p的下一个节点值的绝对值
        m=p->next->val>0?p->next->val:-p->next->val;
        if(q[m]==0){//如果m这个值没有标记过，那么就标记，并保留
            q[m]=1;
            p=p->next;
        }else{//如果已经出现过，那么就删除
            r=p->next;
            p->next=r->next;
            free(r);
        }
    }
    free(q);
    
}
